#include <iostream>
#include <vector>
#include <functional>
using namespace std;

function<void(vector<int> &)> output = [](vector<int> &arr) -> void
{
    int length = arr.size();
    for (int i = 0; i < length; ++i)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
};

function<void(vector<int> &, int, int)> swapInVector = [](vector<int> &arr, int i, int j)
{
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
};

void maxHeap(vector<int> &arr, int i, int heapSize);
void buildMaxHeap(vector<int> &arr);
void maxHeapSort(vector<int> &arr);

void maxHeap(vector<int> &arr, int i, int heapSize)
{
    int left = 2 * i + 1, right = left + 1;
    int largest = i;
    if (left < heapSize && arr[left] > arr[largest])
        largest = left;
    if (right < heapSize && arr[right] > arr[largest])
        largest = right;
    if (largest != i)
    {
        swapInVector(arr, i, largest);
        maxHeap(arr, largest, heapSize);
    }
}

void buildMaxHeap(vector<int> &arr)
{
    //最后一个非叶子节点为arr.size() / 2 - 1
    for (int i = arr.size() / 2 - 1; i >= 0; --i)
    {
        maxHeap(arr, i, arr.size());
    }
}

void maxHeapSort(vector<int> &arr)
{
    buildMaxHeap(arr);
    for (int i = arr.size() - 1; i > 0; --i)
    {
        swapInVector(arr, 0, i);
        maxHeap(arr, 0, i);
    }
}

void minHeap(vector<int> &arr, int i, int heapSize);
void buildMinHeap(vector<int> &arr);
void minHeapSort(vector<int> &arr);

void minHeap(vector<int> &arr, int i, int heapSize)
{
    int left = 2 * i + 1;
    int right = left + 1;
    int smallest = i;
    if (left < heapSize && arr[left] < arr[smallest])
        smallest = left;
    if (right < heapSize && arr[right] < arr[smallest])
        smallest = right;
    if (smallest != i)
    {
        swapInVector(arr, i, smallest);
        minHeap(arr, smallest, heapSize);
    }
}

void buildMinHeap(vector<int> &arr)
{
    for (int i = arr.size() / 2 - 1; i >= 0; --i)
    {
        minHeap(arr, i, arr.size());
    }
}

void minHeapSort(vector<int> &arr)
{
    buildMinHeap(arr);
    for (int i = arr.size() - 1; i > 0; --i)
    {
        swapInVector(arr, 0, i);
        minHeap(arr, 0, i);
    }
}

int main()
{
    vector<int> arr = {6, 2, 1, 3, 5, 4, 9, 7, 5, 4, 11, 2, 9, 4, 7, 3, 8, 10};

    vector<int> temp(arr);
    output(temp);
    maxHeapSort(temp);
    output(temp);

    temp = arr;
    output(temp);
    minHeapSort(temp);
    output(temp);

    return 0;
}
